class TreeNode {
    public value!: number;
    public left?: TreeNode;
    public right?: TreeNode;

    constructor(value: number) {
        this.value = value;
    }

    public add(newNode: TreeNode) {
        if (newNode.value < this.value) {
            if (this.left !== undefined) {
                this.left.add(newNode);
            }
            else {
                this.left = newNode;
            }
        }
        else {
            if (this.right !== undefined) {
                this.right.add(newNode);
            }
            else {
                this.right = newNode;
            }
        }
    }
}

export default class BinarySortTree {
    private root: TreeNode | undefined = undefined;

    public add(value: number) {
        const newNode = new TreeNode(value);
        if (this.root === undefined) {
            this.root = newNode;
        }
        else {
            this.root.add(newNode);
        }
    }

    public middle(node: TreeNode | undefined = this.root, res: number[] = []) {
        if (node !== undefined) {
            if (node.left !== undefined) {
                this.middle(node.left, res);
            }
            res.push(node.value);
            if (node.right !== undefined) {
                this.middle(node.right, res);
            }
        }
        return res;
    }

    public search(value: number) {
        let tempNode: TreeNode | undefined = this.root;
        while (tempNode !== undefined) {
            if (tempNode.value === value) {
                break;
            }
            else if (value < tempNode.value) {
                tempNode = tempNode.left;
            }
            else if (value > tempNode.value) {
                tempNode = tempNode.right;
            }
        }
        return tempNode;
    }

    public searchParent(value: number) {
        let parentNode: TreeNode | undefined = this.root;
        while (parentNode !== undefined) {
            if (value < parentNode.value) {
                if (parentNode.left !== undefined && parentNode.left.value === value) {
                    break;
                }
                else {
                    parentNode = parentNode.left;
                }
            }
            else {
                if (parentNode.right !== undefined && parentNode.right.value === value) {
                    break;
                }
                else {
                    parentNode = parentNode.right;
                }
            }
        }
        return parentNode;
    }

    /**
     * @description 删除节点
     * @param value 节点值
     * @example
     * 1. 找出value对应的节点
     * 2. 找出value对应的父节点
     * 3. 如果删除的节点没有树（即left、right都为undefined），父节点对应的left、right设置为undefined
     * 4. 如果删除的节点只有左节点或右节点，父节点对应的left、right指向仅存在的左右节点
     * 5. 如果删除的节点是一颗树，同时存在左、右子节点，
     *    以该树为基准，找出右子节点的最小值，删除最小值所在的节点，
     *    并将最小值设置为父节点的值
     */
    public remove(value: number) {
        // 待删除节点
        const toDelNode = this.search(value);
        // 父节点
        const parentNode = this.searchParent(value) as TreeNode;
        if (toDelNode === undefined) {
            return;
        }
        if (parentNode === undefined && toDelNode.left === undefined && toDelNode.right === undefined) {
            this.root = undefined;
            return;
        }
        // 1). 待删除节点是叶子节点，没有left、right, 父节点对应的位置为空
        if (toDelNode.left === undefined && toDelNode.right === undefined) {
            if (value < parentNode.value) {
                parentNode.left = undefined;
            } else {
                parentNode.right = undefined;
            }
        }
        // 2). 待删除的节点是树，存在left、right
        else if (toDelNode.left !== undefined && toDelNode.right !== undefined) {
            let temp: TreeNode = toDelNode.right;
            while (temp.left !== undefined) {
                temp = temp.left;
            }
            const tempMinVal = temp.value;
            this.remove(tempMinVal);
            toDelNode.value = tempMinVal;
        }
        // 3). 待删除的节点只存在一个左子节点（或只存在右子节点）
        else {
            let nextNode = toDelNode.left;
            if (nextNode === undefined) {
                nextNode = toDelNode.right;
            }
            if (parentNode === undefined) {
                toDelNode.value = nextNode?.value as number;
                toDelNode.left = nextNode?.left;
                toDelNode.right = nextNode?.right;
            }
            else if (value < parentNode.value) {
                parentNode.left = nextNode;
            }
            else {
                parentNode.right = nextNode;
            }
        }
    }
}